package offer;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @Author Elephas
 * @Date 2022/2/12
 **/
@FunctionalInterface
public interface NumEnclaves {
    int numEnclaves(int[][] grid);
}
class NumEnclavesImpl1 implements NumEnclaves{
    final static int[][] TEST_01 = new int[][]{{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
    final static int[][] TEST_02 = new int[][]{{0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0}, {1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1}, {1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0}, {1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1}, {1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1},{1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0}};

    public static void main(String[] args) {
        new NumEnclavesImpl1().numEnclaves(TEST_02);
    }

    private int m;
    private int n;
    private Set<Long> unvisited;
    private int[][] grid;
    static final int SEA = 0;
    static final int LAND = 1;

    @Override
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        unvisited = new HashSet<>();
        this.grid = grid;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == LAND) {
                    unvisited.add(myHash(i, j));
                }
            }
        }
        // 开始搜索
        int ans = 0;
        while(!unvisited.isEmpty()) {
            long x_y = unvisited.iterator().next();
            // 从点 x,y 开始寻找连通子图
            boolean reachBoundary = false;
            Stack<Long> stack = new Stack<>();
            stack.push(x_y);
            int count = 0;
            while(!stack.isEmpty()){
                long curXY = stack.pop();
                if(unvisited.contains(curXY)){
                    count++;
                    unvisited.remove(curXY);
                    int x = (int) (curXY >>> 32);
                    int y = (int) curXY;
                    grid[x][y] = -1;
                    if (isBoundary(x, y)) {
                        reachBoundary = true;
                    }
                    if (canPush(x - 1, y)) {
                        stack.push(myHash(x - 1, y));
                    }
                    if (canPush(x + 1, y)) {
                        stack.push(myHash(x + 1, y));
                    }
                    if (canPush(x, y - 1)) {
                        stack.push(myHash(x, y - 1));
                    }
                    if (canPush(x, y + 1)) {
                        stack.push(myHash(x, y + 1));
                    }
                }
            }
            if(!reachBoundary){
                ans += count;
            }
        }

        return ans;
    }
    private boolean canPush(int x, int y){
        if(isValidPoint(x, y) && grid[x][y] == LAND){
            Long x_y = myHash(x, y);
            if(unvisited.contains(x_y)){
                return true;
            }
        }
        return false;
    }
    private boolean isValidPoint(int x, int y){
        if(x >= 0 && x < m && y >= 0 && y < n){
            return true;
        }else{
            return false;
        }
    }
    private boolean isBoundary(int x, int y){
        if(x == 0 || x == m - 1 || y == 0 || y == n - 1){
            return true;
        }else{
            return false;
        }
    }

    private long myHash(int x, int y){
        return( ((long) x) << 32) + y;
    }
}
class NumEnclavesImpl2 implements NumEnclaves{

    public static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    private int m;
    private int n;
    private boolean[][] visited;
    @Override
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if(grid[i][j] == 1 && !visited[i][j]){
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
    void dfs(int[][] grid, int row, int col){
        if(row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]){
            return;
        }
        visited[row][col] = true;
        for(int[] dir : dirs){
            dfs(grid,row + dir[0],col + dir[1]);
        }
    }
}
